// https://leetcode.cn/problems/NYBBNL/description/


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

 func midorder(root * TreeNode) (* TreeNode, * TreeNode) {	
	if root == nil {
		return nil, nil
	}
	left, left_tail := midorder(root.Left)
	right, right_tail := midorder(root.Right)
	root.Left = nil
	head, tail := root, root
	if left != nil {
		left_tail.Right = root
		head = left
		tail = root
	}
	if right != nil {
		tail.Right = right
		tail = right_tail
	}
	return head, tail
}


func increasingBST(root *TreeNode) *TreeNode {
	head, _ := midorder(root)
	return head
 }